package demo.practice.dp;

public class P338 {


    public int[] countBits(int n) {
        //这个题确实妙，之前提交过，使用的是暴力解法
        //dp解法思路
        //dp[i]= dp[ i>>1] +  (i&1)
        //i&1 代表最后一位的bit位是1还是0

        //dp[i]代表 i有多少个bit位
        //防止n为0和负数
        if (n <= 0) return new int[1];

        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;


        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i >> 1] + (1 & i);
        }

        return dp;

    }
}
